package com.example.leetdemo.finash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution494 {

    public static int findTargetSumWays(int[] nums, int target) {
        List<Map<Integer, Integer>> list = new ArrayList<>();
        Map<Integer, Integer> first = new HashMap<>();
        first.put(nums[0], 1);
        first.put(-nums[0], first.getOrDefault(-nums[0], 1));
        list.add(first);
        for (int i = 1; i < nums.length; i++) {
            Map<Integer, Integer> latest = list.get(i - 1);
            Map<Integer, Integer> map = new HashMap<>();
            for (Integer key : latest.keySet()) {
                map.put(key - nums[i], map.getOrDefault(key - nums[i], 0) + latest.get(key));
                map.put(key + nums[i], map.getOrDefault(key + nums[i], 0) + latest.get(key));
            }
            list.add(map);
        }
        return list.get(nums.length - 1).get(target);
    }

    public static void main(String[] args) {

    }

    public static int findTargetSumWays2(int[] nums, int target) {

        return 0;
    }

}
